ElmのArrayのその他のパフォーマンス("bulk set"など)
TLDR
ElmのArrayに要素を追加する操作は、やり方によって効率にそこそこ差がある
ユースケースに合わせて実際のデータ構造に対しベンチするのが確実
Bulk Set
入力がListで、それを受け側であるArrayに"bulk set"/"bulk append"のようなことがしたい
受け側のArrayに長さ制限がある(下のベンチマークでは1000)
ここでは仮に、入力は常に受け側のArrayの長さ制限以内に収まるものを考える。収まらない場合は「どう作業を分割するか」も考えなければならないが後で考える
出力としては受け側のArrayが返ってほしい。このとき、出力は長さ制限「以内」であれば良く、必ず上限ぴったりのArrayが返らなくても良い(=短くても良い)
思いついたのは3つで、
2. 受け側のArrayは長さゼロ(あるいはとにかく入力をすべて受け入れても上限を超えない長さ)でinitializeし、入力のListをArray.fromListで一括Array変換してからArray.appendで結合する
3. 受け側のArrayは長さゼロ(あるいはとにかく入力をすべて受け入れても上限を超えない長さ)でinitializeし、入力のListをfoldしながらArray.pushしていく
なんだか面白い傾向が出ている
1. 入力のListをfoldしながら固定長のArrayに1個1個Array.setしていくのが一番遅い。List.foldlに余計なオーバーヘッドがある？大きなサイズのArrayに対する操作にオーバーヘッドがある？
HamtよりArrayのほうが少し速いが、それほど変わらない
2. 入力のListをArray.fromListで一括Array変換してからArray.appendで結合するのが一番速い。受け側のArrayがまだ空の場合も、すでに要素がある場合でも同様
HamtよりArrayのほうが速い
3. 入力のListをfoldしながら1個1個Array.pushしていくのはArray.setよりは速いが、オーダーとしては同程度、つまりやはり遅い
ArrayよりHamtのほうが速い
結論としては、bulkの場合受け側にArrayを使って、入力のListをArray.fromList >> Array.append targetArrayに渡すのが速いということになる。受け側のArrayは最初から制限長でinitializeして扱うと遅い模様で、そうなるとbulkでない、単一のsetについてもそれを活かせるような方式で合わせておくほうが良さそうである
https://gyazo.com/b4f8c33925c7ad0e9b1cae979639d020
Single Set
ということで、単一setについても試した
999-length arrayにappendするケースは何故か失敗していたので図が出てない
劇的に遅い方式というのはないので、どれを使っても良さそうではある
Bulkの場合はそうでもなかったのだが、受け側Arrayの末尾近くにsetする場合、あるいは受け側の要素数がすでにある程度大きいところにappend/pushする場合はHamtのほうが速くなっている
https://gyazo.com/2bce91ea6048fa226bcb60c2baff4379
Length
標的のArrayが制限長に達しているかどうかを知るのにlengthを使うかもしれないので調べた
予想通りではあるが、List.lengthは線形時間O(N)かかり、Array.lengthとHamt.lengthはどちらもO(1)。ArrayとHamtに大きな差はない